#include <stdlib.h>
#include <stdio.h>

typedef int ElemType;
typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;

typedef struct {
    LinkNode *front, *rear;//链表头 链表尾
} LinkQueue;//先进先出
//队列的初始化，使用的是带头结点的链表来实现的
void InitQueue(LinkQueue &Q) {
    //强转类型
    Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));//头和尾指向同一个结点
    //初始化队列，因为没有入队元素，故头即是尾，next置为NULL
    Q.front->next = NULL;//头指针的next指针为NULL
}

bool IsEmpty(LinkQueue Q) {
    if (Q.front == Q.rear) return true;
    else return false;
}

//入队
void EnQueue(LinkQueue &Q, ElemType element) {
    LinkNode *pnew = (LinkNode *) malloc(sizeof(LinkNode));
    pnew->data = element;

    pnew->next = NULL;//当前结点很可能为尾结点（不再入队便自动成为尾结点）
    Q.rear->next = pnew;//尾指针的next指向pnew，因为从尾部入队
    Q.rear = pnew;//rear要指向新的尾部
}

//出队
bool DeQueue(LinkQueue &Q, ElemType &element) {
    //出队就是将头结点指向下一个结点
    if (IsEmpty(Q)) return false;
    LinkNode *q = Q.front->next;//拿到第一个结点，存入
    element = q->data;//获取要出队的元素值
    Q.front->next = q->next;//让第一个结点断链
    if (Q.rear == q) {
        //链表只剩余一个结点时，被删除后，要改变rear
        Q.rear = Q.front;
    }
    free(q);
    return true;
}

//队列的实现(链表)
int main() {
    LinkQueue Q;
    ElemType element;//存储出队元素
    //初始化队列
    InitQueue(Q);

    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    EnQueue(Q, 6);
    EnQueue(Q, 7);

    //出队
    bool ret;
    ret = DeQueue(Q, element);
    if (ret) {
        printf("DeQueue success element is %d\n", element);
    } else {
        printf("DeQueue failed\n");
    };
    return 0;
}
